#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
//void swap(int* a, int* b)
//{
//    int tmp = *a;
//    *a = *b;
//    *b = tmp;
//}
//
//
//
//void adjustdown(vector<int>& nums, int k, int parent)
//{
//    int child = parent * 2 + 1;
//    while (child < k)
//    {
//        if (child + 1 < k && nums[child] > nums[child + 1])
//            child++;
//        if (nums[child] < nums[parent])
//        {
//            swap(&nums[child], &nums[parent]);
//            parent = child;
//            child = parent * 2 + 1;
//
//
//        }
//
//        else
//        {
//            break;
//        }
//
//
//
//    }
//
//
//
//
//
//}
//
//vector<int> topKFrequent(vector<int>& nums, int k) {
//    for (int i = (k - 1 - 1) / 2; i >= 0; i--)
//        adjustdown(nums, k, i);
//
//    for (int i = k; i < nums.size(); i++)
//    {
//        if (nums[i] > nums[0])
//        {
//            nums[0] = nums[i];
//            adjustdown(nums, k, 0);
//
//
//        }
//
//
//
//
//
//    }
//    vector<int>result(nums.begin(), nums.begin() + k);
//    sort(result.begin(), result.end());
//    return result;
//
//}
//    int main()
//    {
//        int arr[]= { 7,1, 5, 3, 6, 4 };
//        vector<int>res(arr, arr + 6);
//        vector<int>ret=topKFrequent(res, 2);
//        vector<int>::iterator it = ret.begin();
//        while (it != ret.end())
//        {
//            cout << *it << endl;
//            it++;
//        }
//    
//    
//    }
int subarraySum(vector<int>& nums, int k) {
    int left = 0;
    int right = 1;
    int count = 0;
    int sum = nums[left]+nums[right];
    while (left < nums.size())
    {
        if (sum < k)
        {
            right++;
            sum += nums[right];


        }
        else if ( sum > k)
        {
            sum -= nums[left];
            left++;


        }
        else
        {
            count++;
            sum -= nums[left];
            left++;


        }







    }


    return count;





}
int main()
{
    int arr[] = { 1,1,1 };
    vector<int> res(arr,arr+3);
   int ret=subarraySum(res,2);
   printf("%d", ret);




}
class Solution {
public:
    void swap(int* a, int* b)
    {
        int tmp = *a;
        *a = *b;
        *b = tmp;






    }






    int mysort(vector<int>& nums, int begin, int end)
    {
        int keyi = begin;
        while (begin < end)
        {
            while (begin < end && nums[end] >= nums[keyi])
                end--;
            while (begin < end && nums[begin] <= nums[keyi])
                begin++;
            swap(&nums[begin], &nums[end]);
        }
        swap(&nums[begin], &nums[keyi]);
        return begin;

    }
    void resort(vector<int>& nums, int begin, int end)
    {
        if (begin >= end)
            return;
        int mid = mysort(nums, begin, end);
        resort(nums, begin, mid - 1);
        resort(nums, mid + 1, end);









    }

    void sortColors(vector<int>& nums) {
        resort(nums, 0, nums.size() - 1);
    }
}; class Solution {
public:
    void swap(int* a, int* b)
    {
        int tmp = *a;
        *a = *b;
        *b = tmp;
    }



    void adjustdown(vector<int>& nums, int k, int parent)
    {
        int child = parent * 2 + 1;
        while (child < k)
        {
            if (child + 1 < k && nums[child] > nums[child + 1])
                child++;
            if (nums[child] < nums[parent])
            {
                swap(&nums[child], &nums[parent]);
                parent = child;
                child = parent * 2 + 1;


            }

            else
            {
                break;
            }



        }





    }
    int findKthLargest(vector<int>& nums, int k) {
        for (int i = (k - 1 - 1) / 2; i >= 0; i--)
            adjustdown(nums, k, i);

        for (int i = k; i < nums.size(); i++)
        {
            if (nums[i] > nums[0])
            {
                nums[0] = nums[i];
                adjustdown(nums, k, 0);


            }





        }
        vector<int>result(nums.begin(), nums.begin() + k);
        sort(result.begin(), result.end());
        return result[0];

    }
}; class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int count = 0;
        int maxp = INT_MIN + 1;
        for (int i = 0; i < nums.size(); i++)
        {
            count += nums[i];
            if (count > maxp)maxp = count;
            if (count < 0)count = 0;




        }
        return maxp;










    }
}; class Solution {
public:




    bool isValid(string s) {
        stack<char>st;
        char* str = &s[0];
        while (*str)
        {
            if (*str == '{' || *str == '(' || *str == '[')
            {
                st.push(*str);
                str++;
            }
            else
            {
                if (st.empty())
                    return false;
                else

                {
                    if (*str == '}' && st.top() == '{' ||
                        *str == ')' && st.top() == '(' ||
                        *str == ']' && st.top() == '[')
                    {
                        st.pop();
                        str++;
                    }
                    else
                    {
                        return false;
                    }





                }





            }









        }
        if (st.empty())
            return true;
        else
            return false;

    }
}; class MinStack {
public:
    stack<int>st1;
    stack<int>st2;

    void push(int val) {
        st1.push(val);
        if (st2.empty() || val <= st2.top())
            st2.push(val);

    }

    void pop() {
        if (st1.top() == st2.top())
        {
            st2.pop();
        }
        st1.pop();


    }

    int top() {
        return st1.top();

    }

    int getMin() {
        return st2.top();

    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 *//**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
 class Solution {
 public:
     vector<int>result;
     vector<int> rightSideView(TreeNode* root) {
         queue<TreeNode*>st;
         if (root != nullptr)
             st.push(root);
         while (!st.empty())
         {
             int sz = st.size();
             vector<int>path;
             while (sz--)
             {
                 TreeNode* find = st.front();
                 path.push_back(find->val);
                 st.pop();
                 if (find->left)
                     st.push(find->left);
                 if (find->right)
                     st.push(find->right);
             }
             result.push_back(path[path.size() - 1]);


         }
         return result;









     }
 }; class Solution {
 public:
     vector<vector<int>> result;
     vector<int>path;
     void backtracking(vector<int>& nums, vector<int>used)
     {
         if (path.size() == nums.size())
         {
             result.push_back(path);
             return;

         }
         for (int i = 0; i < nums.size(); i++)
         {
             if (i > 0 && nums[i - 1] == nums[i] && used[i - 1] == 0)
                 continue;
             if (used[i] == 0)
             {
                 used[i] = 1;
                 path.push_back(nums[i]);
                 backtracking(nums, used);
                 path.pop_back();
                 used[i] = 0;
             }





         }







     }
     vector<vector<int>> permute(vector<int>& nums)
     {
         result.clear();
         path.clear();
         vector<int>used(nums.size(), 0);
         sort(nums.begin(), nums.end());
         backtracking(nums, used);
         return result;












     }
 }; class Solution {
 public:
     vector<vector<int>>result;
     vector<int>path;
     void backtracking(vector<int>& nums, int index)
     {
         result.push_back(path);
         if (index >= nums.size())
         {
             return;
         }
         for (int i = index; i < nums.size(); i++)
         {
             path.push_back(nums[i]);
             backtracking(nums, i + 1);
             path.pop_back();



         }










     }





     vector<vector<int>> subsets(vector<int>& nums) {
         result.clear();
         path.clear();
         backtracking(nums, 0);
         return result;

     }
 }; class Solution {
 public: vector<string>result;
       string path;
       const string map[10] = { " "," ","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz", };
       void backtracking(string digits, int index)
       {
           if (index >= digits.size())
           {
               result.push_back(path);
               return;


           }
           string s = map[digits[index] - '0'];
           for (int i = 0; i < s.size(); i++)
           {
               path.push_back(s[i]);
               backtracking(digits, index + 1);
               path.pop_back();




           }







       }






       vector<string> letterCombinations(string digits) {

           result.clear();
           path.clear();
           if (digits.size() == 0)
               return result;
           backtracking(digits, 0);
           return result;





       }
 }; class Solution {
 public:
     int minPathSum(vector<vector<int>>& grid) {
         vector<vector<int>>dp(grid.size() + 1, vector<int>(grid[0].size() + 1, 0));
         dp[0][1] = 0;
         dp[1][0] = 0;

         for (int i = 0; i < grid.size(); i++)
         {
             dp[i + 1][1] = dp[i][1] + grid[i][0];



         }
         for (int i = 0; i < grid[0].size(); i++)
         {
             dp[1][i + 1] = dp[1][i] + grid[0][i];



         }


         for (int i = 2; i <= grid.size(); i++)
         {
             for (int j = 2; j <= grid[0].size(); j++)

                 dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];


         }
         return dp[grid.size()][grid[0].size()];







     }
 }; class Solution {
 public:
     int longestCommonSubsequence(string text1, string text2) {

         vector<vector<int>>dp(text1.size() + 1, vector<int>(text2.size() + 1, 0));
         dp[0][0] = 0;
         for (int i = 1; i <= text1.size(); i++)
         {

             for (int j = 1; j <= text2.size(); j++)
             {
                 if (text1[i - 1] == text2[j - 1])
                 {
                     dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
                 }
                 else
                 {
                     dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
                 }
             }





         }

         int maxp = 0;
         for (int i = 0; i <= text1.size(); i++)
         {
             for (int j = 0; j <= text2.size(); j++)
             {
                 maxp = max(maxp, dp[i][j]);




             }
         }
         return maxp;





     }
 }; class Solution {
 public:
     vector<int> searchRange(vector<int>& nums, int target) {

         vector<int>res(2, -1);
         vector<int>dat(2, 0);
         int begin = 0;
         int end = nums.size() - 1;
         if (nums.size() == 1 && nums[0] == target)return dat;
         while (begin < end)
         {
             while (begin < end && nums[begin] != target)
                 begin++;
             while (begin < end && nums[end] != target)
                 end--;
             if (nums[begin] == target && nums[end] == target)
             {
                 vector<int>result;
                 result.push_back(begin);
                 result.push_back(end);
                 return result;

             }
             if (begin == end)
                 return res;

         }
         return res;




     }
 }; class Solution {
 public:
     vector<vector<string>> result;
     bool isvalid(vector<string>& chessboard, int row, int col, int n)
     {
         for (int i = 0; i < row; i++)
         {

             if (chessboard[i][col] == 'Q')
                 return false;


         }
         for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; j--, i--)
         {
             if (chessboard[i][j] == 'Q')
                 return false;




         }
         for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++)
         {
             if (chessboard[i][j] == 'Q')
                 return false;




         }


         return true;











     }
     void backtraecking(vector<string>& chessboard, int row, int n)
     {
         if (row == n)
         {
             result.push_back(chessboard);
             return;
         }
         for (int i = 0; i < n; i++)
         {
             if (isvalid(chessboard, row, i, n))
             {
                 chessboard[row][i] = 'Q';
                 backtraecking(chessboard, row + 1, n);
                 chessboard[row][i] = '.';



             }









         }










     }
     vector<vector<string>> solveNQueens(int n) {
         vector<string>chessboard(n, string(n, '.'));
         backtraecking(chessboard, 0, n);
         return result;

     }
 }; class Solution {
 public:
     vector<int> partitionLabels(string s) {
         vector<int>result;
         int hash[27] = { 0 };
         for (int i = 0; i < s.size(); i++)

             hash[s[i] - 'a'] = i;
         int left = 0;
         int right = 0;
         for (int i = 0; i < s.size(); i++)
         {
             right = max(right, hash[s[i] - 'a']);
             if (right == i)
             {
                 result.push_back(right - left + 1);
                 left = right + 1;



             }





         }


         return result;

     }
 }; class Solution {
 public:
     vector<vector<string>> result;
     vector<string>path;
     bool isvalid(string s, int begin, int end)
     {
         while (begin < end)
         {
             if (s[begin] != s[end])
                 return false;
             begin++;
             end--;


         }
         return true;





     }
     void backtracking(string s, int index)
     {
         if (index >= s.size())
         {
             result.push_back(path);
             return;
         }
         for (int i = index; i < s.size(); i++)
         {
             if (isvalid(s, index, i))
             {
                 string str = s.substr(index, i - index + 1);
                 path.push_back(str);
             }
             else
             {
                 continue;
             }
             backtracking(s, i + 1);
             path.pop_back();







         }








     }




     vector<vector<string>> partition(string s) {
         result.clear();
         path.clear();
         backtracking(s, 0);
         return result;










     }
 };